package com.wk.data.tree;
///* 二叉树遍历框架 */
//void traverse(TreeNode root) {
//    // 前序遍历 在此打印root
//    traverse(root.left)
//    // 中序遍历  在此打印root
//    traverse(root.right)
//    // 后序遍历  在此打印root
//}
// 快速排序的逻辑是，若要对nums[lo..hi]进行排序，我们先找一个分界点p，通过交换元素使得nums[lo..p-1]都小于等于nums[p]，且nums[p+1..hi]都大于nums[p]，
// 然后递归地去nums[lo..p-1]和nums[p+1..hi]中寻找新的分界点，最后整个数组就被排序了。
//void sort(int[] nums, int lo, int hi) {
//    /****** 前序遍历位置 ******/
//    // 通过交换元素构建分界点 p
//    int p = partition(nums, lo, hi);
//    /************************/
//
//    sort(nums, lo, p - 1);
//    sort(nums, p + 1, hi);
//}
//归并排序的逻辑，若要对nums[lo..hi]进行排序，我们先对nums[lo..mid]排序，再对nums[mid+1..hi]排序，最后把这两个有序的子数组合并，整个数组就排好序了。
//void sort(int[] nums, int lo, int hi) {
//    int mid = (lo + hi) / 2;
//    sort(nums, lo, mid);
//    sort(nums, mid + 1, hi);
//
//    /****** 后序遍历位置 ******/
//    // 合并两个排好序的子数组
//    merge(nums, lo, mid, hi);
//    /************************/
//}
public class TraverseDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BST treeBst = new BST();
		treeBst.insert(2);
		treeBst.insert(3);
		treeBst.insert(4);
		System.out.println(count(treeBst.root));
	}
	public static int count(TreeNode root) {
		if(root == null) {
			return 0;
		}
		return 1+ count(root.left)+count(root.right);
	}
	
	// 将整棵树的节点翻转
	public static TreeNode invertTree(TreeNode root) {
	    // base case
	    if (root == null) {
	        return null;
	    }

	    /**** 前序遍历位置 ****/
	    // root 节点需要交换它的左右子节点
	    TreeNode tmp = root.left;
	    root.left = root.right;
	    root.right = tmp;

	    // 让左右子节点继续翻转它们的子节点
	    invertTree(root.left);
	    invertTree(root.right);

	    return root;
	}
}
